﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.DataStructures.Maps;
using Algoritmia.Utils;

namespace Algoritmia.DataStructures.DoubleEndedPriorityMaps
{
    public class IntervalHeapMap<TKey,TValue> : IDoubleEndedPriorityMap<TKey,TValue>
    {
        private readonly Func<int, IMap<TKey, int>> _createMap;
        private readonly Func<IMap<TKey,int>, TKey, IMap<TKey, int>> _redimensionMap;
        private readonly EqualityComparison<KeyValuePair<TKey, TValue>> _firstHasHigherPriority;
        private readonly EqualityComparison<KeyValuePair<TKey, TValue>> _firstHasLowerPriority;

        private int _capacity;
        private int _count;
        private KeyValuePair<TKey, TValue>[] _heap;
        private IMap<TKey, int> _index;

        private readonly ValuesView<TKey,TValue> _valuesView;
        private readonly ItemsView<TKey, TValue> _itemsView;

        public IntervalHeapMap(IEnumerable<KeyValuePair<TKey,TValue>> items = null,
            int capacity = 0,
            EqualityComparison<KeyValuePair<TKey,TValue>> firstHasHigherPriority = null,
            Func<int,IMap<TKey,int>> createMap = null,
            Func<IMap<TKey,int>, TKey, IMap<TKey,int>> redimensionMap = null)
        {
            _createMap = createMap ?? (n => AlgoritmiaFactory.Maps<TKey, int>.Default);
            _redimensionMap = redimensionMap ?? ((map, k) => map);

            _firstHasHigherPriority = GetHigherPriorityFunction(firstHasHigherPriority);
            _firstHasLowerPriority =  ((value1, value2) => _firstHasHigherPriority(value2, value1));

            if (items != null)
            {
                _heap = items.ToArray();
                _count = _heap.Length;
                if (capacity > _count)
                {
                    _capacity = capacity;
                    Array.Resize(ref _heap, _capacity);
                }
                else
                {
                    _capacity = _count > 0 ? _count : 1;
                }
            }
            else
            {
                _capacity = capacity > 0 ? capacity : 1;
                _heap = new KeyValuePair<TKey, TValue>[_capacity];
                _count = 0;
            }

            _index = _createMap(_capacity);
            for(var i = 0; i < _count; i++)
            {
                _index.Add(_heap[i].Key,i);
            }
            for(var i = 0; i < _count; i+=2)
            {
                if ( i + 1 < _count)
                {
                    SwapBrothers(i);   
                }
            }
            int lastParent = Parent(_count - 1);

            for (int i = lastParent; i >= 0; i -= 2)
            {
                HeapifyHigher(i);
                HeapifyLower(i);
            }

            _valuesView = new ValuesView<TKey, TValue>(this);
            _itemsView = new ItemsView<TKey, TValue>(this);
        }

        private static EqualityComparison<KeyValuePair<TKey, TValue>> GetHigherPriorityFunction(
            EqualityComparison<KeyValuePair<TKey, TValue>> firstHasHigherPriority)
        {
            if (firstHasHigherPriority == null)
            {
                if (typeof (TValue).GetInterfaces().Contains(typeof (IComparable<TValue>)))
                {
                    if (typeof (TKey).GetInterfaces().Contains(typeof (IComparable<TKey>)))
                    {
                        return (kv1, kv2) => Comparer<TValue>.Default.Compare(kv1.Value, kv2.Value) == 0
                                                 ? Comparer<TKey>.Default.Compare(kv1.Key, kv2.Key) < 0
                                                 : Comparer<TValue>.Default.Compare(kv1.Value, kv2.Value) < 0;
                    }

                    return (kv1, kv2) => Comparer<TValue>.Default.Compare(kv1.Value, kv2.Value) < 0;
                }
                throw new ArgumentException("No comparison criterium on non comparable data.");

            }
            return firstHasHigherPriority;
        }

        private bool SwapBrothers(int index)
        {
            if ( _firstHasHigherPriority(_heap[index+1],_heap[index]))
            {
                Swap(index,index+1);
                return true;
            }
            return false;
        }

        private void Swap(int i, int j)
        {
            KeyValuePair<TKey, TValue> aux = _heap[j];

            _index[_heap[j].Key] = i;
            _index[_heap[i].Key] = j;

            _heap[j] = _heap[i];
            _heap[i] = aux;
        }

        private void HeapifyLower(int index)
        {
            int lowest = index+1;
            while(true)
            {
                foreach(int child in Children(index))
                {
                    if ( child +1 < _count)
                    {
                        if (_firstHasLowerPriority(_heap[child+1],_heap[lowest]))
                        {
                            lowest = child + 1;
                        }
                    }
                    else
                    {
                        if (_firstHasLowerPriority(_heap[child], _heap[lowest]))
                        {
                            lowest = child;
                        }
                    }
                }
                if (lowest == index + 1) break;
                Swap(lowest, index + 1);
                index = lowest/2*2;
                if ( index + 1 < _count)
                {
                    SwapBrothers(index);
                }
                else
                {
                    break;
                }
            }
        }

        private void HeapifyHigher(int index)
        {
            int highest = index;
            while (true)
            {
                foreach(int child in Children(index))
                {
                    if (_firstHasHigherPriority(_heap[child],_heap[highest]))
                    {
                        highest = child;
                    }
                }
                if (highest == index) break;
                Swap(highest,index);
                index = highest;
                if ( index + 1 < _count)
                {
                    SwapBrothers(index);
                }

            }
        }

        private void BubbleUpLower(int index)
        {
            while (true)
            {
                int parent = Parent(index);
                if (parent == index) break;
                if (_firstHasLowerPriority(_heap[index + 1], _heap[parent + 1]))
                {
                    Swap(parent + 1, index + 1);
                    index = parent;
                }
                else break;
            }
        }

        private void BubbleUpHigher(int index)
        {
            while (true)
            {
                int parent = Parent(index);
                if (parent == index) break;
                if (_firstHasHigherPriority(_heap[index], _heap[parent]))
                {
                    Swap(parent, index);
                    index = parent;
                }
                else
                {
                    break;
                }
            }
        }

        private IEnumerable<int> Children(int parent)
        {
            int child = 2*(parent + 1);
            if (child < _count)
            {
                yield return child;
            }
            child += 2;
            if (child < _count)
            {
                yield return child;
            }
        }


        private int Parent(int index)
        {
            return ((index / 2 - 1) / 2) * 2;
        }

        private void DoubleCapacity()
        {
            _capacity *= 2;
            Array.Resize(ref _heap,_capacity);
        }

        #region IDoubleEndedPriorityMap<TKey,TValue> Members

        public KeyValuePair<TKey, TValue> GetWorst()
        {
            if ( _count == 0)
            {
                throw new InvalidOperationException("Is not possible to get the worst element from an empty IntervalHeapMap");
            }
            if ( _count == 1)
            {
                return _heap[0];
            }
            return _heap[1];
        }

        public KeyValuePair<TKey, TValue> ExtractWorst()
        {
            if (_count == 0)
            {
                throw new InvalidOperationException("Is not possible to extract the worst element from an empty IntervalHeapMap");
            }
            if ( _count == 1)
            {
                _count--;
                _index.Remove(_heap[0].Key);
                return _heap[0];
            }
            if ( _count == 2)
            {
                _count--;
                _index.Remove(_heap[1].Key);
                return _heap[1];
            }
            KeyValuePair<TKey, TValue> retValue = _heap[1];
            Swap(1,_count-1);
            _index.Remove(retValue.Key);
            _count--;
            HeapifyLower(0);
            return retValue;
            
        }

        #endregion

        #region IPriorityMap<TKey,TValue> Members

        public KeyValuePair<TKey, TValue> GetOptimal()
        {
            if ( _count == 0)
            {
                throw new InvalidOperationException("Is not possible to get the optimal element from an empty IntervalHeapMap");
            }
            return _heap[0];
        }

        public KeyValuePair<TKey, TValue> ExtractOptimal()
        {
            if ( _count == 0)
            {
                throw new InvalidOperationException("Is not possible to extract the optimal element from an empty IntervalHeapMap");
            }
            if ( _count == 1)
            {
                _count--;
                _index.Remove(_heap[0].Key);
                return _heap[0];
            }
            KeyValuePair<TKey, TValue> retValue = _heap[0];
            _index.Remove(retValue.Key);
            Swap(0, _count - 1);
            _count--;
            if (_count >= 2)
            {
                HeapifyHigher(0);
            }
            return retValue;
        }

        #endregion

        #region IMap<TKey,TValue> Members

        public TValue this[TKey key]
        {
            get
            {
                if ( !_index.Contains(key))
                {
                    throw new KeyNotFoundException(key.ToString());
                }
                return _heap[_index[key]].Value;

            }
            set
            {
                if (_index.Contains(key))
                { 
                    //If the key exists in the map.
                    int i = _index[key];
                    int ii = i%2 == 0 ? i : i - 1;
                    var oldKvp = _heap[i];
                    var newKvp = new KeyValuePair<TKey, TValue>(key, value);
                    _heap[i] = newKvp;
                    if (ii + 1 < _count)
                    {
                        if (SwapBrothers(ii))
                        {
                            oldKvp = _heap[i];
                            if (_firstHasHigherPriority(oldKvp, newKvp))
                            {
                                BubbleUpLower(ii);
                                HeapifyHigher(ii);
                            }
                            else
                            {
                                BubbleUpHigher(ii);
                                HeapifyLower(ii);
                            }
                        }
                        else
                        {
                            if (_firstHasHigherPriority(oldKvp, newKvp))
                            {
                                if (ii == i)
                                {
                                    HeapifyHigher(ii);
                                }
                                else
                                {
                                    BubbleUpLower(ii);
                                }
                            }
                            else if (_firstHasLowerPriority(oldKvp, _heap[i]))
                            {
                                if (ii == i)
                                {
                                    BubbleUpHigher(ii);
                                }
                                else
                                {
                                    HeapifyLower(ii);
                                }
                            }
                        }
                    }
                }
                else
                {
                    //if the key does not exist in the map.
                    if (_count == 0)
                    {
                        _count++;
                        _heap[0] = new KeyValuePair<TKey, TValue>(key,value);
                        _index[key] = 0;
                    }
                    else
                    {
                        if (_count == _capacity)
                        {
                            DoubleCapacity();
                        }
                        _index = _redimensionMap(_index, key);
                        int indexOfNewValue = _count;
                        _heap[indexOfNewValue] = new KeyValuePair<TKey, TValue>(key, value);
                        _index[key] = indexOfNewValue;
                        _count++;
                        if (_count%2 == 0)
                        {
                            //if the last node has a brother
                            if (SwapBrothers(indexOfNewValue - 1))
                            {
                                BubbleUpHigher(indexOfNewValue - 1);
                            }
                            else
                            {
                                BubbleUpLower(indexOfNewValue - 1);
                            }
                        }
                        else
                        {
                            //if the last node hasn't a brother
                            int parent = Parent(indexOfNewValue);
                            if (_firstHasHigherPriority(_heap[parent], _heap[indexOfNewValue]) &&
                                _firstHasLowerPriority(_heap[parent + 1], _heap[indexOfNewValue]))
                            {
                                return;
                            }
                            if ( _firstHasHigherPriority(_heap[indexOfNewValue],_heap[parent]))
                            {
                                Swap(indexOfNewValue, parent);
                                BubbleUpHigher(parent);
                            }
                            if (_firstHasLowerPriority(_heap[indexOfNewValue],_heap[parent+1]))
                            {
                                Swap(indexOfNewValue,parent+1);
                                BubbleUpLower(parent);
                            }
                        }
                    }
                }
            }
        }


        public void Add(TKey key, TValue value)
        {
            this[key] = value;
        }

        public bool Contains(TKey key)
        {
            return _index.Contains(key);
        }

        public TValue Get(TKey key, TValue defaultValue)
        {
            if (_index.Contains(key))
                return _heap[_index[key]].Value;
            return defaultValue;
        }

        public ICollectionView<TKey> Keys()
        {
            return _index.Keys();
        }

        public ICollectionView<KeyValuePair<TKey, TValue>> Items()
        {
            return _itemsView;
        }

        public bool Remove(TKey key)
        {
            if (!_index.Contains(key))
                return false;
            TKey newKey = _heap[_count - 1].Key;
            TValue newValue = _heap[_count - 1].Value;
            _count--;
            int i = _index[key];
            _index.Remove(key);
            if (i != _count-1)
            {
                _index[newKey] = i;
                this[newKey] = newValue;
            }
            return true;
        }

        public TValue SetDefault(TKey key, TValue defaultValue)
        {
            if (_index.Contains(key))
                return _heap[_index[key]].Value;
            this[key] = defaultValue;
            return defaultValue;
        }

        public ICollectionView<TValue> Values()
        {
            return _valuesView;
        }

        #endregion

        #region IEnumerable<KeyValuePair<TKey,TValue>> Members

        public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
        {
            return (from e in _heap
                    select e).GetEnumerator();
        }

        #endregion

        #region IEnumerable Members

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        #endregion

        #region ICountable Members

        public int Count
        {
            get { return _count; }
        }

        #endregion

        public override string ToString()
        {
            return String.Format("{0} <{1},{2}> [{3}]", GetType().Name, typeof (TKey).Name, typeof (TValue).Name,
                                 string.Join(",", this));
        }
    }
}
